import sys
from typing import List


class Solution:
    def check(self, nums: List):
        target = nums[3]
        if nums[1] == 0 or nums[0] == 0 or nums[2] == 0:
            return 0

        def dfs(num: int):
            if num > target:
                return 0
            elif num == target:
                return 1

            return dfs(num + nums[1]) + dfs(num * nums[2])

        out = dfs(nums[0])
        return out


if __name__ == '__main__':
    t = int(sys.stdin.readline().strip())

    lines = []
    for _ in range(t):
        line = sys.stdin.readline().strip()
        line = list(map(int, line.split(' ')))
        lines.append(line)

    s = Solution()
    for i in range(t):
        o = s.check(lines[i])
        if o > 0:
            print(1)
        else:
            print(0)
